package LC;

import java.util.Stack;

/**
 * https://leetcode.com/problems/reverse-nodes-in-k-group/description/
 * Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
 * k is a positive integer and is less than or equal to the length of the linked list.
 * If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
 * You may not alter the values in the nodes, only nodes itself may be changed.
 * Only constant memory is allowed.
 * For example,
 * Given this linked list: 1->2->3->4->5
 * For k = 2, you should return: 2->1->4->3->5
 * For k = 3, you should return: 3->2->1->4->5
 */
public class LC_025_ReverseNodesInKGroup_LinkedList {
    public static void main(String[] args) {
        ListNode head1 = new ListNode(0);
        head1.next = new ListNode(1);
        head1.next.next = new ListNode(2);
        head1.next.next.next = new ListNode(3);
        head1.next.next.next.next = new ListNode(4);
        head1.next.next.next.next.next = new ListNode(6);

        ListNode head2 = new ListNode(0);
        head2.next = new ListNode(1);
        head2.next.next = new ListNode(2);
        head2.next.next.next = new ListNode(3);
        head2.next.next.next.next = new ListNode(4);
        head2.next.next.next.next.next = new ListNode(6);

        printList(head1);
        ListNode h1 = Solution_1.reverseKGroup(head1, 3);
        printList(h1);
        ListNode h2 = Solution_2.reverseKGroup(head2, 3);
        printList(h2);
    }

    static class ListNode {
        int val;

        ListNode next;

        public ListNode(int x) {
            this.val = x;
        }
    }

    private static void printList(ListNode head) {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    static class Solution_1 {
        private static ListNode reverseKGroup(ListNode head, int k) {
            Stack<ListNode> st = new Stack<>();
            ListNode temp = head;
            for (int i = 0; i < k; i++) {
                if (head != null)
                    st.push(head);
                else
                    return temp;
                head = head.next;
            }
            ListNode first = st.pop();
            ListNode res = first;
            for (int i = 0; i < k - 1; i++) {
                first.next = st.pop();
                first = first.next;
            }
            first.next = reverseKGroup(head, k);
            return res;
        }
    }

    static class Solution_2 {
        static ListNode reverseKGroup(ListNode head, int k) {
            ListNode root = new ListNode(-1);
            root.next = head;
            ListNode res = root;
            ListNode temp = head;
            int i = 0;
            while (temp != null) {
                i++;
                temp = temp.next;
            }
            while (i >= k) {
                for (int j = 0; j < k - 1; j++) {
                    ListNode node = root.next;
                    root.next = head.next;
                    head.next = root.next.next;
                    root.next.next = node;
                }
                root = head;
                head = head.next;
                i -= k;
            }
            return res.next;
        }
    }
}
